package com.example.leetcode;

/**
 *航班预订统计
 */
public class Demo1109 {

    public static void main(String[] args) {
        int[][] ints=new int[][]{{1,2,10},{2,3,20},{ 2, 5, 25}};
        corpFlightBookings3(ints, 5);
    }

    /**
     * 暴力解法===超出时间
     * @param bookings
     * @param n
     * @return
     */
    public static int[] corpFlightBookings1(int[][] bookings, int n) {
        int[] results=new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < bookings.length; j++) {
                int[] booking=bookings[j];
                if (booking[0]<=i+1 && booking[1]>=i+1){
                    results[i]+=booking[2];
                }
            }
        }
        return results;
    }

    /**
     * 遍历思路2
     * @param bookings
     * @param n
     * @return
     */
    public static int[] corpFlightBookings2(int[][] bookings, int n) {
        int[] results=new int[n];
        for (int j = 0; j < bookings.length; j++) {
            int[] booking=bookings[j];
            for (int i = 0; i <= booking[1] - booking[0]; i++) {
                results[i+booking[0]-1]+=booking[2];
            }
        }
        return results;
    }

    /**
     * 差分法
     * @param bookings
     * @param n
     * @return
     */
    public static int[] corpFlightBookings3(int[][] bookings, int n) {
        int[] results=new int[n];
        for (int[] booking : bookings) {
            results[booking[0]-1]+=booking[2];
            if (booking[1]<n){
                results[booking[1]]-=booking[2];
            }
        }
        for (int i = 1; i < n; i++) {
            results[i]+=results[i-1];
        }

        return results;
    }
}
